package features.advance.leetcode.geometry.doublepointer.easy;

/**
 * 28. 实现 strStr()
 * 难度  简单
 *
 * 实现 strStr() 函数。
 *
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * 示例 1:
 *
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 *
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 * 说明:
 *
 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 */
public class Solution28 {

    // function to convert character to integer
    public int charToInt(int idx, String s) {
        return (int)s.charAt(idx) - (int)'a';
    }

    /**
     * 有 O(N)O(N) 复杂度的解法嘛？答案是有的，有两种方法可以实现：
     *
     * Rabin-Karp，通过哈希算法实现常数时间窗口内字符串比较。
     *
     * 比特位操作，通过比特掩码来实现常数时间窗口内字符串比较。
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        int L = needle.length(), n = haystack.length();
        if (L > n) return -1;

        // base value for the rolling hash function
        int a = 26;
        // modulus value for the rolling hash function to avoid overflow
        long modulus = (long)Math.pow(2, 31);

        // compute the hash of strings haystack[:L], needle[:L]
        long h = 0, ref_h = 0;
        for (int i = 0; i < L; ++i) {
            h = (h * a + charToInt(i, haystack)) % modulus;
            ref_h = (ref_h * a + charToInt(i, needle)) % modulus;
        }
        if (h == ref_h) return 0;

        // const value to be used often : a**L % modulus
        long aL = 1;
        for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;

        for (int start = 1; start < n - L + 1; ++start) {
            // compute rolling hash in O(1) time
            h = (h * a - charToInt(start - 1, haystack) * aL
                    + charToInt(start + L - 1, haystack)) % modulus;
            if (h == ref_h) return start;
        }
        return -1;
    }

    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "lo";
//        haystack = "missississppi";
//        needle = "ississp";
//        haystack = "aaa";
//        needle = "aaaa";
//        haystack = "mississippi";
//        needle = "issipi";
        int len = new Solution28() {
            @Override
            public int strStr(String haystack, String needle) {
                if (haystack == null || needle == null || needle.length() == 0) return 0;
                if (haystack.length() == 0 || haystack.length() < needle.length()) return -1;
                int i = 0;
                int index = -1;
                int len = needle.length();
                for (int j = 0; j < haystack.length(); j++) {
                    if (haystack.charAt(j) == needle.charAt(i)) {
                        if (i == 0) index = j;
                        i++;
                        if (i == len) return index;
                    } else {
                        if (index != -1) {
                            i = 0;
                            j = index;
                            index = -1;
                        }
                    }
                }

                return -1;
            }
        }.strStr(haystack, needle);
        System.out.println(len);
    }
}
